//== SAGITTARIUS ============================================================================

//== BEGINNING OF CODE ===============================================================

#include "sagittarius/core/SagittariusCore.h"
#include "sagittarius/lexer/lAST.h"
#include "sagittarius/io/io.h"

/// lAST_createNode
lASTNode* lAST_createNode() {
    lASTNode* n = LX_ALLOC(sizeof(lASTNode));
    AN(n, "lAST_createNode: malloc failure");
    
    //init cs
    n->cs = NULL;
    //init deriv class
    n->d = NULL;
    
    //initialize members:
    n->n1 = NULL;
    n->n2 = NULL;
    
    //initialize properties
    n->inv = 0;
    n->closed = 0;
    n->nullable = 0;
    
    n->p = NULL;
    
    return n;
}

/// lAST_deepCopy
lASTNode* lAST_deepCopy(const lASTNode* m) {
    lASTNode* n = LX_ALLOC(sizeof(lASTNode));
    
    //init type
    n->type = m->type;
    
    //init cs
    if(m->cs)
        n->cs = re_copyCS(m->cs);
    else
        n->cs = NULL; //d'oh!
    
    //init deriv class
    if(m->d)
        n->d = re_deepcopyDC(m->d);
    else
        n->d = NULL;
    
    //initialize properties
    n->inv = m->inv;
    n->closed = m->closed;
    n->nullable = m->nullable;
    
    //FIXME: no way to copy data (not really a problem atm)
    n->p = NULL;
    
    if(m->n1)
        n->n1 = lAST_deepCopy(m->n1);
    else
        n->n1 = NULL;
    if(m->n2)
        n->n2 = lAST_deepCopy(m->n2);
    else
        n->n2 = NULL;
    
    return n;
}

/// lAST_shallowCopy
lASTNode* lAST_shallowCopy(const lASTNode* m) {
    lASTNode* n = LX_ALLOC(sizeof(lASTNode));
    
    //init type
    n->type = m->type;
    
    //init cs
    if(m->cs)
        n->cs = re_copyCS(m->cs);
    else
        n->cs = NULL; //d'oh!
    
    //init deriv class
    if(m->d)
        n->d = m->d; //FIXME: how deep to copy DC?
    else
        n->d = NULL;
    
    //initialize properties
    n->inv = m->inv;
    n->closed = m->closed;
    n->nullable = m->nullable;
    
    //FIXME: no way to copy data (not really a problem atm)
    n->p = NULL;
    
    if(m->n1)
        n->n1 = m->n1;
    else
        n->n1 = NULL;
    if(m->n2)
        n->n2 = m->n2;
    else
        n->n2 = NULL;
    
    return n;
}

/// lAST_destroy_node
void lAST_destroy_node(lASTNode* n) {
    if(n->cs)
        re_destroyCS(n->cs);
    if(n->d)
        re_destroyDC(n->d);
    if(n->n1)
        lAST_destroy_node(n->n1);
    if(n->n2)
        lAST_destroy_node(n->n2);
    if(n->p) {
        #if SAGITTARIUS_LXALPHA_USE_GMP
        LX_FREE_BUFFER(n->p);
        #else
        LX_FREE(n->p);
        #endif
    }
    LX_FREE(n);
}

/// lAST_destroyShallow
void lAST_destroyShallow(lASTNode* n) {
    if(n->cs)
        LX_FREE(n->cs);
    if(n->d)
        re_destroyDC(n->d);
    LX_FREE(n);
}

/// lex_computeDC
void lex_computeDC(lASTNode* n) {
    //TODO: is the lemma violated when a backref is present? Yes.
    //FIXME: case when backrefs are present
    if(n->n1 && !n->n1->d)
        lex_computeDC(n->n1);
    if(n->n2 && !n->n2->d)
        lex_computeDC(n->n2);
    AZ(n->d);
    //SG_WRITE(1, "DC Node:\n");
    //lex_printOut(2, n, 0);
    if(n->type == AST_NODE_TYPE_REPRIMITIVE) {
        if(re_CSisEmptyStr(n->cs) || re_CSisNull(n->cs))
            n->d = re_DCFull();
        else
            n->d = re_DCSingle(n->cs);
        /*SG_WRITE(1, "DC Single:\n");
        re_writeDC(1, n->d);
        SG_WRITE(1, "\n");*/
    } else {
        n->d = re_DCMesh(n->n1->d, n->n2->d);
        /*SG_WRITE(1, "DC Mesh:\n");
        re_writeDC(1, n->d);
        SG_WRITE(1, "\n");*/
    }
    //SG_WRITE(1, "\n");
}

/// lex_compare
int lex_compare(const lASTNode* r, const lASTNode* s) {
    //type specifies major order
    if(r->type < s->type)
        return LEX_COMPARE_LT;
    else if(r->type > s->type)
        return LEX_COMPARE_GT;
    //same type:
    if(r->type == AST_NODE_TYPE_REPRIMITIVE && s->type == AST_NODE_TYPE_REPRIMITIVE) {
        /*int compres = re_compareCS(r->cs, s->cs);
        SG_WRITE(2, "CS Compare result: ");
        sg_writeInt(2, compres);
        SG_WRITE(2, "\n");*/
        return 4-re_compareCS(r->cs, s->cs); //compare charsets
    }
	{
		int z = lex_compare(r->n1, s->n1); //dictionary order on {n1, n2}
		if(z != LEX_COMPARE_EQ)
			return z;
		//FIXME: support Kleene closure & complement
		z = lex_compare(r->n2, s->n2); //if these are equal then the expressions are equal
		return z;
	}
}

/// lex_constructSymbol
lASTNode* lex_constructSymbol(LXConstAlphaType c) {
    lASTNode* n = lAST_createNode();
    n->type = AST_NODE_TYPE_REPRIMITIVE;
    n->cs = re_createCSSym(c);
    if(LX_CMPALPHA_EQ_SPC(c, CONST_RE_EMPTY_STR))
        n->nullable = 1;
    return n;
}

/// lex_constructFixed
lASTNode* lex_constructFixed(LXFixedType c) {
    lASTNode* n = lAST_createNode();
    n->type = AST_NODE_TYPE_REPRIMITIVE;
    n->cs = re_createCSFixed(c);
    if(c == CONST_RE_EMPTY_STR)
        n->nullable = 1;
    return n;
}

/// lex_constructEmptyStr
lASTNode* lex_constructEmptyStr() {
    return lex_constructFixed(CONST_RE_EMPTY_STR);
}

/// lex_constructNull
lASTNode* lex_constructNull() {
    return lex_constructFixed(CONST_RE_NULL);
}

/// lex_isEmptyString
int lex_isEmptyString(lASTNode* n) {
    if(n->type == AST_NODE_TYPE_REPRIMITIVE && re_CSisEmptyStr(n->cs))
        return 1;
    else
        return 0;
}

/// lex_isNull
int lex_isNull(lASTNode* n) {
    if(n->type == AST_NODE_TYPE_REPRIMITIVE && re_CSisNull(n->cs))
        return 1;
    else
        return 0;
}

/// lex_commCanonical2
//void lex_commCanonical2(lASTNode** r, lASTNode** s, const lASTNode* p, const lASTNode* q)
//can't do const when using pool
void lex_commCanonical2(lASTNode** r, lASTNode** s, lASTNode* p, lASTNode* q) {
    //commutative dominance
#if !LX_USE_POOLALLOC
    if(lex_compare(p,q) != LEX_COMPARE_GT) {
        *r = lAST_deepCopy(p);
        *s = lAST_deepCopy(q);
    } else {
        *r = lAST_deepCopy(q);
        *s = lAST_deepCopy(p);
    }
#else
    if(lex_compare(p,q) != LEX_COMPARE_GT) {
        *r = p;
        *s = q;
    } else {
        *r = q;
        *s = p;
    }
#endif
}

#if 0
/// lex_commCanonical3
void lex_commCanonical3(lASTNode** r, lASTNode** s, lASTNode** t, const lASTNode* a, const lASTNode* b, const lASTNode* c) {
#if !LX_USE_POOLALLOC
    //commutative dominance
    if(lex_compare(a,b) != LEX_COMPARE_GT) {
        //a <= b
        if(lex_compare(b,c) != LEX_COMPARE_GT) {
            //b <= c
            *r = lAST_deepCopy(a);
            *s = lAST_deepCopy(b);
            *t = lAST_deepCopy(c);
        } else if(lex_compare(a,c) != LEX_COMPARE_GT) {
            //a <= c < b
            *r = lAST_deepCopy(a);
            *s = lAST_deepCopy(c);
            *t = lAST_deepCopy(b);
        } else {
            //c < a <= b
            *r = lAST_deepCopy(c);
            *s = lAST_deepCopy(a);
            *t = lAST_deepCopy(b);
        }
    } else {
        //b < a
        if(lex_compare(a,c) != LEX_COMPARE_GT) {
            //b < a <= c
            *r = lAST_deepCopy(b);
            *s = lAST_deepCopy(a);
            *t = lAST_deepCopy(c);
        } else if(lex_compare(b,c) != LEX_COMPARE_GT) {
            //b <= c < a
            *r = lAST_deepCopy(b);
            *s = lAST_deepCopy(c);
            *t = lAST_deepCopy(a);
        } else {
            //c < b < a
            *r = lAST_deepCopy(c);
            *s = lAST_deepCopy(b);
            *t = lAST_deepCopy(a);
        }
    }
#else
    //commutative dominance
    if(lex_compare(a,b) != LEX_COMPARE_GT) {
        //a <= b
        if(lex_compare(b,c) != LEX_COMPARE_GT) {
            //b <= c
            *r = a;
            *s = b;
            *t = c;
        } else if(lex_compare(a,c) != LEX_COMPARE_GT) {
            //a <= c < b
            *r = a;
            *s = c;
            *t = b;
        } else {
            //c < a <= b
            *r = c;
            *s = a;
            *t = b;
        }
    } else {
        //b < a
        if(lex_compare(a,c) != LEX_COMPARE_GT) {
            //b < a <= c
            *r = b;
            *s = a;
            *t = c;
        } else if(lex_compare(b,c) != LEX_COMPARE_GT) {
            //b <= c < a
            *r = b;
            *s = c;
            *t = a;
        } else {
            //c < b < a
            *r = c;
            *s = b;
            *t = a;
        }
    }
#endif
}

/// lex_assocCanonical
void lex_assocCanonical(lASTNode** r, lASTNode** s, const lASTNode* p, const lASTNode* q, lAST_NodeType type) {
    //associative dominance
    //right-associative
    if( (p->type == AST_NODE_TYPE_REUNION || p->type == AST_NODE_TYPE_REINTERSECTION) && 
        q->type == AST_NODE_TYPE_REPRIMITIVE ) {
        *s = lAST_createNode();
        (*s)->type = p->type;
        //TODO: set s->nullable
        lex_commCanonical3(r, &(*s)->n1, &(*s)->n2, p->n1, p->n2, q);
        if(p->type == AST_NODE_TYPE_REUNION)
            if( p->nullable || q->nullable)
                (*s)->nullable = 1;
        if(p->type == AST_NODE_TYPE_REINTERSECTION)
            if( p->nullable && q->nullable)
                (*s)->nullable = 1;
    } else
        lex_commCanonical2(r, s, p, q);
}
#endif

/// lex_constructNodeUnion
lASTNode* lex_constructNodeUnion(lASTNode* r, lASTNode* s) {
    lASTNode* n;
    
    if(lex_isNull(r)) {
        if(lex_isNull(s)) {
            //both null
            return lex_constructNull();
        }
#if !LX_USE_POOLALLOC
        return lAST_deepCopy(s);
#else
        return s;
#endif
    }
    if(lex_isNull(s) || lex_compare(r,s) == LEX_COMPARE_EQ) {
#if !LX_USE_POOLALLOC
        return lAST_deepCopy(r);
#else
        return r;
#endif
    }
    n = lAST_createNode();
    n->type = AST_NODE_TYPE_REUNION;
    if( r->nullable || r->nullable)
        n->nullable = 1;
    lex_commCanonical2(&n->n1, &n->n2, r, s);
    return n;
}

/// lex_constructNodeConcat
lASTNode* lex_constructNodeConcat(lASTNode* r, lASTNode* s) {
    lASTNode* n;
    
    if(lex_isEmptyString(r)) {
        return lAST_deepCopy(s);
    }
    if(lex_isEmptyString(s)) {
        return lAST_deepCopy(r);
    }
    if(lex_isNull(r) || lex_isNull(s)) {
        return lex_constructNull();
    }
    
    n = lAST_createNode();
    n->type = AST_NODE_TYPE_RECONCAT;
#if !LX_USE_POOLALLOC
    n->n1 = lAST_deepCopy(r);
    n->n2 = lAST_deepCopy(s);
#else
    n->n1 = r;
    n->n2 = s;
#endif
    n->cs = NULL;
    AZ(n->cs);
    return n;
}

/// lex_constructNodeInt
lASTNode* lex_constructNodeInt(lASTNode* r, lASTNode* s) {
    lASTNode* n;
    
    if(lex_isNull(r) || lex_isNull(s)) {
        return lex_constructNull();
    }
    if(lex_compare(r,s) == LEX_COMPARE_EQ) {
#if !LX_USE_POOLALLOC
        return lAST_deepCopy(r);
#else
        return r;
#endif
    }
    //if one term is a primitive, then may be able to resolve expression as a primitive
    n = lAST_createNode();
    n->type = AST_NODE_TYPE_REINTERSECTION;
    if( r->nullable && r->nullable)
        n->nullable = 1;
    lex_commCanonical2(&n->n1, &n->n2, r, s);
    return n;
}

/// lAST_swap
void lAST_swap(lASTNode** r, lASTNode** s) {
    lASTNode *a = *r;
    *r = *s;
    *s = a;
}

#if 0
/// lAST_sortRHC
void lAST_sortRHC(lASTNode* n) {
    //this is a Gnome sort impl
    //it could definitely be more efficient, but this works well with the data structure
    //nodes must be in RH canonical form for this to work
    if(n->type == AST_NODE_TYPE_REUNION || n->type == AST_NODE_TYPE_REINTERSECTION)
        if(n->n1->type != n->type)
            if(n->n2->type == n->type) {
                if(lex_compare(n->n1,n->n2->n1) == LEX_COMPARE_GT) {
                    //keep going
                    lAST_sortRHC(n->n2);
                    lAST_swap(&n->n1, &n->n2->n1);
                }
            } else {
                if(lex_compare(n->n1,n->n2) == LEX_COMPARE_GT)
                    lAST_swap(&n->n1, &n->n2);
            }
}
#endif

/// lAST_sortRHC
void lAST_sortRHC(lASTNode* n) {
    //this is a Gnome sort impl
    //it could definitely be more efficient, but this works well with the existing data structure
    //nodes must be in RH canonical form for this to work
    if(n->type == AST_NODE_TYPE_REUNION || n->type == AST_NODE_TYPE_REINTERSECTION) {
        if(n->n2->type != n->type) {
            //terminal
            if(lex_compare(n->n1,n->n2) == LEX_COMPARE_GT)
                lAST_swap(&n->n1, &n->n2);
        }else if(n->n1->type != n->type) {
            lAST_sortRHC(n->n2);
            if(lex_compare(n->n1,n->n2->n1) == LEX_COMPARE_GT) {
                lAST_swap(&n->n1, &n->n2->n1);
                lAST_sortRHC(n->n2);
            }
        }
    }
}

/// lAST_canonicalize
void lAST_canonicalize(lASTNode** _n) {
    lASTNode* n=*_n;
    RE_CharSet* cs;
    int closed;
    int nullable=0;
    int do_sort=0;
    
    if(n->type == AST_NODE_TYPE_REPRIMITIVE)
        return; //nothing to do for primitives
    
    //associative dominance
    //TODO: concatenate nodes can be associated
    //TODO: do not apply to backrefs
    if(n->type == AST_NODE_TYPE_REUNION || n->type == AST_NODE_TYPE_REINTERSECTION) {
        /*if(n->n1->type == AST_NODE_TYPE_REPRIMITIVE && n->n2->type == AST_NODE_TYPE_REPRIMITIVE)
            if(lex_compare(n->n1,n->n2) == LEX_COMPARE_GT)
                lAST_swap(&n->n1, &n->n2);*/
        lASTNode *a;
        while(n->n1->type == n->type) {
            //move right
            //TODO: reevaluate nullable
            a = n->n1;
            n->n1 = n->n1->n1;
            a->n1 = a->n2;
            a->n2 = n->n2;
            n->n2 = a;
            
            do_sort = 1; //this structure will need sorting later
        }
    }
    
    //canonicalize child nodes
    if(n->n1)
        lAST_canonicalize(&n->n1);
    if(n->n2)
        lAST_canonicalize(&n->n2);
    
    if(n->type == AST_NODE_TYPE_REUNION || n->type == AST_NODE_TYPE_REINTERSECTION) {
        if(n->n1->type == AST_NODE_TYPE_REPRIMITIVE && n->n2->type == AST_NODE_TYPE_REPRIMITIVE) {
            //can usually simplify
            //distribute complement
            if(n->inv) {
                cs = re_CSComplement(n->n1->cs);
                LX_FREE(n->n1->cs);
                n->n1->cs = cs;
                cs = re_CSComplement(n->n2->cs);
                LX_FREE(n->n2->cs);
                n->n2->cs = cs;
                n->inv = 0;
                if(n->type == AST_NODE_TYPE_REUNION)
                    n->type = AST_NODE_TYPE_REINTERSECTION;
                else if(n->type == AST_NODE_TYPE_REINTERSECTION)
                    n->type = AST_NODE_TYPE_REUNION;
//                 SG_WRITE(2, "Children canonicalized:\n");
//                 lex_writeOut(2, n, 0);
                //now go ahead and simplify further if applicable
            }
            closed = n->closed;
            //union
            if(n->type == AST_NODE_TYPE_REUNION) {
                //compute nullable
                if(n->n1->nullable || n->n2->nullable)
                    nullable = 1;
                //merge character classes
                cs = re_CSUnion(n->n1->cs, n->n2->cs);
                re_CSSortInPlace(cs);
#if !LX_USE_POOLALLOC
                lAST_destroy_node(*_n);
#else
                lAST_destroyShallow(*_n);
#endif
                *_n = lAST_createNode();
                n=*_n;
                n->type = AST_NODE_TYPE_REPRIMITIVE;
                n->cs = cs;
                n->closed = closed;
                n->nullable = nullable || closed;
                return;
            }
            //intersection
            if(n->type == AST_NODE_TYPE_REINTERSECTION) {
                //compute nullable
                if(n->n1->nullable && n->n2->nullable)
                    nullable = 1;
                //merge character classes
                cs = re_CSIntersect(n->n1->cs, n->n2->cs);
                re_CSSortInPlace(cs);
#if !LX_USE_POOLALLOC
                lAST_destroy_node(*_n);
#else
                lAST_destroyShallow(*_n);
#endif
                *_n = lAST_createNode();
                n=*_n;
                n->type = AST_NODE_TYPE_REPRIMITIVE;
                n->cs = cs;
                n->closed = closed;
                n->nullable = nullable || closed;
                return;
            }
        } else {
            //AN(0);
            //union/int without primitive leafs: apply commutative law
            /*if(lex_compare(n->n1,n->n2) == LEX_COMPARE_GT) {
                //AN(0);
                lAST_swap(&n->n1, &n->n2);
            }*/
        }
    }
    
    //TODO: do not apply to backrefs
    if(do_sort)
        lAST_sortRHC(n);
    else {
        if((n->type == AST_NODE_TYPE_REUNION || n->type == AST_NODE_TYPE_REINTERSECTION) &&
            (n->n1->type == n->n2->type)) {
            lASTNode *tmp;
            //apply commutation
            if(lex_compare(n->n1, n->n2) == LEX_COMPARE_GT) {
                tmp = n->n1;
                n->n1 = n->n2;
                n->n2 = tmp;
            }
        }
    }
}

/// lex_printNodeType
void lex_printNodeType(int fd, const lAST_NodeType type) {
    //TODO: do not apply to backrefs
    switch(type) {
/*        case AST_NODE_TYPE_ASSN:
            SG_WRITE(1, "Assignment");
            break;
        case AST_NODE_TYPE_ID:
            SG_WRITE(1, "ID");
            break;*/
        case AST_NODE_TYPE_REPRIMITIVE:
            SG_WRITE(fd, "Primitive");
            break;
        case AST_NODE_TYPE_RECONCAT:
            SG_WRITE(fd, "Concat");
            break;
        case AST_NODE_TYPE_REUNION:
            SG_WRITE(fd, "Union");
            break;
        case AST_NODE_TYPE_REINTERSECTION:
            SG_WRITE(fd, "Intersection");
            break;
        default:
            SG_WRITE(fd, "Unknown");
    }
}

/// lex_printOut
void lex_writeOut(int fd, const lASTNode* n, int n_indent) {
    int i;
    
    // leading indent
    for(i=0; i<n_indent; ++i) SG_WRITE(fd, " ");
    
    //negation
    if(n->inv) SG_WRITE(fd, "^");
    //type
    lex_printNodeType(fd, n->type);
    //symbol info for primitives
    if(n->type == AST_NODE_TYPE_REPRIMITIVE) {
        AN(n->cs);
        SG_WRITE(fd, "(");
        re_writeCS(fd, n->cs);
        SG_WRITE(fd, ")");
    }
    //name of id
    /*if(n->type == AST_NODE_TYPE_ID) {
        SG_WRITE(fd, "(");
        LX_WRITE_BUF(1, (constLexBuf)n->p);
        SG_WRITE(fd, ")");
    }*/
    //closure
    if(n->closed) SG_WRITE(fd, "*");
    
    //nullable
    SG_WRITE(fd, " ");
    SG_WRITE(fd, "𝜈 = ");
    sg_writeInt(fd, n->nullable);
    
    SG_WRITE(fd, "\n");
    
    //propagate to children
    if(n->n1) {
        lex_writeOut(fd, n->n1, n_indent+2);
    }
    if(n->n2) {
        lex_writeOut(fd, n->n2, n_indent+2);
    }
}